1. Field of the Invention
The present invention generally relates to digital printing and, more particularly, to digital printing methods using error diffusion (ED) but without the usual problems of anisotropy associated with ED methods.
2. Background Description
Error diffusion, as first described in “An Adaptive Algorithm for Spatial Greyscale” by R. W. Floyd and L. Steinberg in Proceeding of the SID 17/2, (1976) pp. 75-77, is a popular technique for halftoning used today and is considered to be one of the best, and the best among the techniques with similar operating time. This technique and others are reviewed in the book Digital Halftoning, MIT Press, Cambridge, Mass. 1987, by R. Ulichney which is a general reference for digital halftoning. H. Kang, Color Technology for Electronic Imaging Devices, SPIE Optical Engineering Press, Bellingham Washington (1997) is another general reference on digital printing, including digital color printing.
See also, J. F. Jarvis, C. N. Judice, W. H. Ninke, “A Survey of Techniques for the Display of Continuous Tone Pictures on Bilevel Displays”, Computer Graphics and Image Processing, 5, pp. 13-40 (1976), P. Stucki, “MECCA-A Multiple Error Correction Computation Algorithm for BiLevel Image Hardcopy Reproduction”, IBM Res. Rep RZ1060 (1981), for introductory papers on Black and White (BW) ED that is designed for greysclale images. Color images can then treated using such ED on the fundamental colors Cyan (C), Magenta (M), Yellow (Y), and optionally Black (K), since K=C+M+Y, but using a separate K is more economical and usually provides a sharper black.
U.S. Pat. No. 5,070,413 to J. R. Sullivan, R. L. Miller, and T. J. Wetzel for “Color Digital Halftoning with Vector Error Diffusion” discloses ED working directly in the full color space (one sometimes speaks of Vector Error Diffusion (VED) in this case).
U.S. Pat. No. 6,101,001 to C. P. Tresser and C. W. Wu for “Target Patterns Controlled Error Management” provides a description of a multitude of different algorithms of Error Diffusion.
See J. P. Allebach and B. E. Rogowitz, eds., Proceedings, SPIE—The International Society for Optical Engineering: Human Vision, Visual Processing, and Digital Display IV, vol. 1913, (San Jose, Calif.), SPIE, February 1993, for a collection of reprints that cover digital halftoning until 1993.
See also, U.S. Pat. No. 6,614,556 to D.-E Hong, C.-W Kim, and G.-N Boo for “Apparatus for Quantizing a Digital Image by Using an Error Diffusion Coefficient and Threshold Modulation in Zigzag Quantization”, U.S. Pat. No. 6,333,793 to K. Kobayashi for “Image Quality in Error Diffusion Scheme”, U.S. Pat. No. 6,307,647 to A. C. Cheung, S. M. Heydinger, and S. T. Love for “Digital Halftoning With Error Diffusion”, U.S. Pat. No. 6,160,921 to G. G. Marcu for “Error Diffusion with Homogeneous Distribution in Highlight and Shadow Regions”, U.S. Pat. No. 5,684,932 to J. S. Shu for “Method and Apparatus for Dither Array Generation to Reduce Artifacts in Halftoned Image Data Utilizing Ink Reduction Processing”, U.S. Pat. No. 5,668,638 to K. T. Knox for “Error Diffusion Method with Symmetric Enhancement”, U.S. Pat. No. 5,592,592 to J. S. Shu for “Method and Apparatus for Minimizing Artifacts in Images Produced by Error Diffusion Halftoning Utilizing Ink Reduction Processing”, U.S. Pat. No. 5,521,989 to Z. Fan for “Balanced Error Diffusion System”, U.S. Pat. No. 5,467,201 to Z. Fan for “Iterative Error Diffusion System”,U.S. Pat. No. 5,051,844 to J. R. Sullivan for “Digital Halftoning with Error Diffusion”, and U.S. Pat. No. 4,654,721 to G. Goertzel and G. R. Thompson for “System for Reproducing Multi-Level Digital Images on a Bi-Level Printer of Fixed Dot Size”, Qing Yu and Kevin J. Parker, “Stochastic Screen Design using Symmetric Error Compensation”, University of Rochester (1997), and Ashish Jagmohan, Anshul Sehgal and Narendra Ahuja, “Isotropic Error Diffusion Halftoning”, University of Illinois, for a collection of attempts at solving the problem of anisotropy in ED, with partial results.
The problem of the consequences of anisotropy in ED (in particular the consequences on image quality) is considered as still mostly open despite the significant progresses which have been made since ED was invented, and as represented by the cited prior art.
Although considered a high quality method, ED is marred with the problem that it is strongly anisotropic as the result depends strongly on the raster utilized to enumerate the pixels on a page. ED generates worm-like patterns, and other artifacts at the scale of the pixels. These artifacts affect the quality of the image, and are indeed attributed to the very anisotropic character of the algorithm.
The importance of this invention is increased at a time when ink-jet printers arrive in the high end market and (the computational and data handling parts of the) processing times are bound to decrease dramatically for a few more years according to the perspective one has on the progress of core Information Technologies (IT), a decrease that one expects will be faster than the decrease in the mechanical part of the processing (actual printing and paper handling).